![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
An algorithms key schedule is the mechanism that distributes key material to the different parts of the cipher that need it, expanding the key material in the process. This is necessary for three reasons:
When key schedules are poorly designed, they often lead to strange cipher properties: large classes of equivalent keys, self-inverse keys, and so forth. These properties can often aid an attacker in a real-world attack. For example, the DES weak (self-inverse) keys have been exploited in many attacks on larger cryptographic mechanisms built from DES [Knu95a], and the S-1 [Anon95] cipher was broken due to a bad key-schedule design [Wag95a]. Even worse, they can make attacks on the cipher easier, and some attacks on the cipher will be focused directly at the key schedule, such as related-key differential attacks [KSW96, KSW97]. These attacks can be especially devastating when the cipher is used in a hash function construction.
Key schedules can be divided into several broad categories [CDN98]. In some key schedules, knowledge of a round subkey uniquely specifies bits of other round subkeys. In some ciphers the bits are just reused, as in DES, IDEA, and LOKI; and in others some manipulation of the round subkeys is required to determine the other round subkeys: e.g., CAST and SAFER. Other key schedules are designed so that knowledge of one round subkey does not directly specify bits of other round subkeys. Either the round subkey itself is used to generate the other round subkeys in some cryptographically secure manner, as in RC5 and CS-Cipher [SV98], or a one-way function is used to generate the round subkeys (sometimes the block cipher itself): e.g., Blowfish, Serpent [BAK98], ICE11 [Kwa97], and Shark.
11ICE was cryptanalyzed in [RKR98].
Some simple design principles guided our development of the key schedule for Twofish:
The key schedule design of some other ciphers has led to various undesirable properties. These properties, such as the existence of equivalent keys; DES-style weak, semi-weak, and quasi-weak keys; and DES-style complementation properties do not necessarily make the cipher weak. However, they tend to make it harder to use the cipher securely. With our key schedule, we can make convincing arguments that none of these properties exists.
Key schedules vary widely in performance. The DES key schedule can be computed in less than the time required to do one encryption. The Blowfish key schedule requires the time equivalent to 521 encryptions to complete. Most other algorithms fall somewhere in the middle.
For large messages, performance of the key schedule is minor compared to performance of the encryption and decryption functions. For smaller messages, key setup can overwhelm encryption speed. In the design of Twofish, we tried to balance these two items. Our performance criteria included:
12In its comments on the AES criteria, the NSA suggested that a goal should be that two blocks could be enciphered with different keys in virtually the same time as two blocks could be enciphered with the same key [McD97]. The cynical reader would immediately conclude that the NSA is concerned with the efficiency of their brute-force keysearch machines. However, there axe implementations where key agility is a valid concern. Key-stretching techniques can always be used to frustrate brute-force attacks [QDD86, KSHW98]. A better defense, of course, is to always use keys too laxge to make a brute-force search practicable, and to generate them randomly.
If security were not an issue, we would design a simple key schedule where the key bits were used in some natural order, like Skipjack, or with some minimal shuffling, like DES and IDEA. However, these key schedules cause weaknesses when the block cipher is used as a one-way hash function.
If performance were not an issue, it would make sense to simply use a one-way hash function to expand the key into the subkeys and S-box entries, as is done in Khufu, Blowfish, and SEAL. However, the AES efficiency requirements make such an approach unacceptable.
Balancing these two requirements led us to design a relatively simple key schedule with a very complicated analysis.
Previous | Table of Contents | Next |